package com.study.daily.algozuo.y2021.m12.day1212;

/**
 * @author Tom on 2021/12/12
 */
public class Code01_ConvertedToLetter {

    public static void main(String[] args) {
        String s = "11";
        System.out.println(convertToLetter(s));
        System.out.println(dp1(s));
        System.out.println(dp2(s));
    }

    public static int convertToLetter(String s) {
        return process(s, 0);
    }

    public static int process(String s, int index) {
        if (index == s.length()) {
            return 1;
        }
        if (s.charAt(index) == '0') {
            return 0;
        }
        int way1 = process(s, index + 1);
        int way2 = 0;
        if (index + 1 < s.length() && (
                s.charAt(index) - '1' == 0 || s.charAt(index) - '2' == 0 && s.charAt(index) - '7' < 0)) {
            way2 = process(s, index + 2);
        }
        return way1 + way2;
    }

    public static int dp1(String s) {
        int N = s.length();
        int[] dp = new int[N + 1];
        dp[N] = 1;
        for (int i = N - 1; i >= 0; i--) {
            if (s.charAt(i) == '0') {
                dp[i] = 0;
            } else {
                int way1 = dp[i + 1];
                int way2 = 0;
                if (i + 1 < s.length() && (
                        s.charAt(i) - '1' == 0 || s.charAt(i) - '2' == 0 && s.charAt(i) - '7' < 0)) {
                    way2 = dp[i + 2];
                }
                dp[i] = way1 + way2;
            }
        }
        return dp[0];
    }

    public static int dp2(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int N = s.length();
        int[] dp = new int[N];
        if (s.charAt(0) == '0') {
            return 0;
        }
        dp[0] = 1;
        for (int i = 1; i < N; i++) {
            if (s.charAt(i) == '0') {
                if (s.charAt(i - 1) == '0' || s.charAt(i - 1) > '2' || (i - 2 >= 0 && dp[i - 2] == 0)) {
                    return 0;
                } else {
                    dp[i] = i - 2 >= 0 ? dp[i - 2] : 1;
                }
            } else {
                dp[i] = dp[i - 1];
                if (s.charAt(i-1) != '0'&&(s.charAt(i - 1) - '0') * 10 + s.charAt(i) - '0' <= 26) {
                    dp[i] += i-2>=0? dp[i-2]: 1;
                }
            }
        }
        return dp[N - 1];
    }
}
